UVa/10199 - Tourist guide/Intentando ayudar/10199.cpp

   1 #include<stdio.h>
   2 #include<string.h>
   3 #define MAX 106
   4
   5 #define WHITE 0
   6 #define GRAY 1
   7 #define BLACK 2
   8
   9 int a[MAX][MAX], n;
  10 int color[MAX], d[MAX], low[MAX], pre[MAX], used[MAX];
  11
  12 char AP[MAX][33];
  13 int apN;
  14
  15 char city[MAX][33];
  16
  17 int  time;
  18
  19 void init()
  20 {
  21    int i, j;
  22    for(i=0; i<n; i++)
  23    {
  24       color[i]=0;
  25       pre[i]=-1;
  26       used[i]=0;
  27    }
  28    for(i=0; i<n; i++)
  29       for(j=0; j<n; j++)
  30          a[i][j]=0;
  31 }
  32
  33 void DFS_Visit(int u)
  34 {
  35    color[u] = GRAY;
  36    time = time+1;
  37    d[u] = time;
  38    low[u]=time;
  39    int gr=-1, i, fl=0;
  40    for(i=0; i<n; i++)
  41       if(a[u][i]==1)
  42       {
  43         if(color[i] == WHITE)
  44         {
  45            pre[i]=u;
  46            a[i][u]=0;
  47           DFS_Visit(i);
  48
  49           fl++;
  50           if(pre[u]==-1)
  51           {
  52              if(fl==2 && used[u]==0)
  53              {
  54                 used[u]=1;
  55                strcpy(AP[apN], city[u]);
  56                apN++;
  57                continue;
  58              }
  59           }
  60           else if(low[i]>=d[u] && used[u]==0)
  61           {
  62              used[u]=1;
  63              strcpy(AP[apN], city[u]);
  64              apN++;
  65           }
  66           else if(low[i]<low[u])
  67           {
  68              low[u]=low[i];
  69           }
  70         }
  71         else if(color[i]==GRAY)
  72         {
  73            if(d[i]<low[u])
  74               low[u]=d[i];
  75         }
  76         else if(color[i]==BLACK)
  77         {
  78            if(low[i]<low[u])
  79               low[u]=low[i];
  80         }
  81        }
  82
  83    color[u] = BLACK;
  84    time = time+1;
  85 }
  86
  87
  88 int fndL(char *s)
  89 {
  90    int i;
  91    for(i=0; i<n; i++)
  92       if(strcmp(city[i], s)==0)
  93          return i;
  94 }
  95
  96
  97 int main()
  98 {
  99   //freopen("in.txt", "r", stdin);
 100    int test=0,  i, j, x, y,m, v;
 101    char s1[33], s2[33], tmp[33];
 102
 103    while(scanf("%d", &n)==1 && n)
 104    {
 105       for(i=0; i<n; i++)
 106          scanf("%s", city[i]);
 107
 108       scanf("%d", &m);
 109       init();
 110       for(i=0; i<m; i++)
 111       {
 112          scanf("%s %s", &s1, &s2);
 113          x=fndL(s1);
 114          y=fndL(s2);
 115          a[x][y]=1;
 116          a[y][x]=1;
 117       }
 118       apN=0;
 119       time=0;
 120       for(i=0; i<n; i++)
 121          DFS_Visit(i);
 122       if(test)
 123          puts("");
 124       printf("City map #%d: %d camera(s) found\n", test+1, apN);
 125       test++;
 126       for(i=0; i<apN; i++)
 127          for(j=i+1; j<apN; j++)
 128             if(strcmp(AP[i], AP[j])>0)
 129             {
 130                strcpy(tmp, AP[i]);
 131                strcpy(AP[i], AP[j]);
 132                strcpy(AP[j], tmp);
 133             }
 134       for(i=0; i<apN; i++)
 135          printf("%s\n", AP[i]);
 136
 137    }
 138    return 0;
 139 }